package 双指针三指针;
import java.util.*;
/**
 * 该类用于对包含0、1、2的数组进行排序。
 * 提供多种排序方法：两次遍历、计数排序、快速排序。
 */
public class sortColors {
    /**
     * 使用两次遍历的方法对数组进行排序。
     * 第一次遍历将0移到数组前面，第二次遍历将1移到0的后面。
     * @param nums 待排序的数组
     */
    public void twoLoop(int[] nums) {
        int ptr = 0; // 指向当前要交换的位置
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) { // 如果当前元素是0
                swap(nums, ptr, i); // 交换元素
                ptr++; // 移动指针
            }
        }
        for(int i = ptr; i < nums.length; i++) {
            if(nums[i] == 1) { // 如果当前元素是1
                swap(nums, ptr, i); // 交换元素
                ptr++; // 移动指针
            }
        }
    }

    /**
     * 交换数组中的两个元素。
     * @param nums 数组
     * @param a 第一个元素的索引
     * @param b 第二个元素的索引
     */
    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a]; // 临时变量
        nums[a] = nums[b]; // 交换元素
        nums[b] = tmp; // 交换元素
    }

    /**
     * 使用计数排序的方法对数组进行排序。
     * 统计0、1、2的个数，然后重新填充数组。
     * @param nums 待排序的数组
     */
    public void useCount(int[] nums) {
        int red = 0; // 0的个数
        int white = 0; // 1的个数
        for(int num : nums) {
            if(num == 0) red++; // 统计0的个数
            else if(num == 1) white++; // 统计1的个数
        }
        for(int i = 0; i < nums.length; i++) {
            if(i < red) nums[i] = 0; // 填充0
            else if(i < red + white) nums[i] = 1; // 填充1
            else nums[i] = 2; // 填充2
        }
    }

    /**
     * 使用快速排序对数组进行排序。
     * @param nums 待排序的数组
     */
    public void sortCol(int[] nums) {
        // Arrays.sort(nums);
        quickSort(nums, 0, nums.length - 1); // 调用快速排序
    }

    /**
     * 快速排序算法。
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     */
    private void quickSort(int[] nums, int left, int right) {
        if(left >= right) return; // 如果左边界大于等于右边界，返回
        int pivot = partition(nums, left, right); // 获取基准元素的位置
        quickSort(nums, left, pivot - 1); // 递归排序左半部分
        quickSort(nums, pivot + 1, right); // 递归排序右半部分
    }

    /**
     * 分区函数，用于快速排序。
     * @param nums 待排序数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的位置
     */
    private int partition(int[] nums, int left, int right) {
        int val = nums[left]; // 选择第一个元素作为基准
        while(left < right) {
            while(left < right && nums[right] >= val) right--; // 从右向左找小于基准的元素
            nums[left] = nums[right]; // 将小于基准的元素放到左边
            while(left < right && nums[left] <= val) left++; // 从左向右找大于基准的元素
            nums[right] = nums[left]; // 将大于基准的元素放到右边
        }
        nums[left] = val; // 将基准元素放到最终位置
        return left; // 返回基准元素的位置
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取数组，并输出排序后的数组。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s = sc.nextLine().split(","); // 读取数组
        int[] nums = new int[s.length]; // 创建数组
        for(int i = 0; i < s.length; i++) {
            nums[i] = Integer.parseInt(s[i]); // 解析数组
        }
        sortColors scl = new sortColors(); // 创建对象
        scl.twoLoop(nums); // 使用两次遍历的方法排序
        // scl.sortCol(nums); // 使用快速排序
        // scl.useCount(nums); // 使用计数排序
        System.out.println(Arrays.toString(nums)); // 输出排序后的数组
        sc.close(); // 关闭扫描器
    }
}
